 ///
 /// @file    LRUCache.cc
 /// @author  lemon(haohb13@gmail.com)
 /// @date    2022-01-27 09:58:51
 ///
 
#include <list>
#include <iostream>
#include <unordered_map>
using std::cout;
using std::endl;
using std::list;
using std::unordered_map;

//提出问题：该类的对象需要进行复制，是否需要提供复制控制函数?
class LRUCache
{
public:
	LRUCache(size_t capacity)
	: _capacity(capacity)
	{}

	LRUCache(const LRUCache & rhs)
	: _capacity(rhs._capacity)
	, _data(rhs._data)
	//, _hashmap(rhs._hashmap)
	{
		//这里是必须要重新遍历的，并生成相应的hashmap的记录
		//否则复制就是失败的，会发生迭代器紊乱的问题
		auto iter = _data.begin();
		for(; iter != _data.end(); ++iter) {
			_hashmap[iter->key] = iter;
		}
	}

	LRUCache & operator=(const LRUCache & rhs)
	{
		//四部曲的思路是相通的，具体的实现有所差异
		if(this != &rhs) {
			_capacity = rhs._capacity;
			_data = rhs._data;
			_hashmap.clear();

			//重建hashmap的过程
			auto iter = _data.begin();
			for(; iter != _data.end(); ++iter) {
				_hashmap[iter->key] = iter;
			}
		}
		return *this;
	}

	int get(int key);
	void put(int key, int value);

private:
	struct CacheNode
	{
		int key;
		int value;
		CacheNode(int k, int v)
		: key(k), value(v)
		{}
	};
	using iterator = list<CacheNode>::iterator;

	size_t _capacity;
	list<CacheNode> _data;//list的头部保存是最近被访问过的元素，那么尾部自然就成为最近最少被访问过的元素
	unordered_map<int, iterator> _hashmap;//当使用默认的复制控制操作，
										  //那iterator指向的是原来的被复制的list中的节点位置信息
};

void LRUCache::put(int key, int value)
{
	auto iter = _hashmap.find(key);
	if(iter != _hashmap.end()) {
		//1. key存在, 需要修改对应的value的值
		//还需要将该节点放到list的头部
		iter->second->value = value;
		_data.splice(_data.begin(), _data, iter->second);//O(1)
		//更新其在_hashmap中的位置
		_hashmap[key] = _data.begin();
	} else {
		//2. key不存在
		if(_data.size() == _capacity) {
			//已经达到了容量的上限
			//需要淘汰list末尾的元素
			int key = _data.back().key;
			_data.pop_back();
			auto iter = _hashmap.find(key);
			_hashmap.erase(iter);
		}
		_data.push_front(CacheNode(key, value));
		_hashmap[key] = _data.begin();
	}
}

int LRUCache::get(int key)
{
	//key存在
	auto iter = _hashmap.find(key);
	if(iter != _hashmap.end()) {
		//查找到该元素之后，还需要更新在list中的位置
		_data.splice(_data.begin(), _data, iter->second);
		_hashmap[key] = _data.begin();
		return iter->second->value;
	} else {
		return -1;
	}
}
 
void test0() 
{
	LRUCache lrucache(2);
	lrucache.put(1, 1);
	lrucache.put(2, 2);
	cout << "get(1):" << lrucache.get(1) << endl;
	lrucache.put(3, 3);
	cout << "get(2):" << lrucache.get(2) << endl;
	lrucache.put(4, 4);
	cout << "get(1):" << lrucache.get(1) << endl;
	cout << "get(3):" << lrucache.get(3) << endl;
	cout << "get(4):" << lrucache.get(4) << endl;
} 
 
int main(void)
{
	test0();
	return 0;
}








